package hard;

/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
 * Note: 提供的缺省代码仅供参考，可自行根据答题需要进行使用、修改或删除。
 */

import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * OJ考题代码：CI任务调度
 *
 * @author 命题组
 * @since 2020-06-20
 */

public class Hua17 {
    /**
     * main入口由OJ平台调用
     */
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int resourcesNum = cin.nextInt();
        int taskNums = cin.nextInt();
        int colNums = 2;
        int[][] taskAttributes = new int[taskNums][colNums];
        for (int row = 0; row < taskNums; row++) {
            for (int col = 0; col < colNums; col++) {
                taskAttributes[row][col] = cin.nextInt();
            }
        }
        cin.close();
        int result = taskScheduler(resourcesNum, taskAttributes);
        System.out.println(result);
    }
    private static int taskScheduler(int resourcesNum, int[][] taskAttributes) {
        if(resourcesNum>=taskAttributes.length){
            int maxvalue=-1;
            for(int[] item : taskAttributes ){
                maxvalue=Math.max(maxvalue,item[0]);
            }
            return maxvalue;
        }

        return MYtaskScheduler(resourcesNum,taskAttributes);
    }
    private static int MYtaskScheduler(int resourcesNum, int[][] taskAttributes) {
        // 在此补充你的代码
        Arrays.sort(taskAttributes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    // 如果优先级相同，按照时间从大到小排序
                    return Integer.compare(o2[0], o1[0]);
                } else {
                    // 按照优先级从小到大排序
                    return Integer.compare(o1[1], o2[1]);
                }
            }
        });

        Stack<int[]> tasks=new Stack<>();
        for(int i=taskAttributes.length-1;i>=0;i--){
            tasks.push(taskAttributes[i]);
        }
        Map<Integer,Integer> vms=new HashMap<>();
        for(int i=1;i<=resourcesNum;i++){
            vms.put(i,tasks.peek()[0]);
            tasks.pop();
        }
        int totalTime=0;
        while(!tasks.empty()){
            List<Integer> re=vmstart(vms);
            totalTime+=re.get(0);
            for(int i=1;i<re.size() && !tasks.empty();i++){
                vms.put(re.get(i),tasks.peek()[0]);
                tasks.pop();
            }
        }
        int maxvalue=-1;
        for(Map.Entry<Integer, Integer> entry : vms.entrySet()){
            int value = entry.getValue();
            if (value > maxvalue) {
                maxvalue = value;
            }
        }
        totalTime+=maxvalue;
        return totalTime;
    }

    private static List<Integer> vmstart(Map<Integer,Integer> vms){
        int minvalue=Integer.MAX_VALUE;

        for(Map.Entry<Integer, Integer> entry : vms.entrySet()){
            int value = entry.getValue();
            if (value < minvalue&& value>0) {
                minvalue = value;

            }
        }
        List<Integer> indexs=new ArrayList<>();
        indexs.add(minvalue);
        int result[];
        for(Map.Entry<Integer, Integer> entry : vms.entrySet()) {
            entry.setValue(entry.getValue() - minvalue);
            if(entry.getValue()==0){
                indexs.add(entry.getKey());
            }
        }

        return indexs;
    }
}
